Talk:Infinite time Turing machine
I'm pretty sure \(\lambda\) is larger than \(\omega_1^{\text{CK}}\). Deedlit11 (talk) 06:17, October 2, 2013 (UTC) Wait, if \(\Sigma\) is not admissible, is it than equal to or larger than \(\omega_1^{\text{DEF}}\)? Wythagoras (talk) 16:41, October 2, 2013 (UTC) :The first limit of admissible ordinals is \(\omega_\omega^\text{CK}\), so probably \(\Sigma\) is this ordinal. Ikosarakt1 (talk ^ ) 17:02, October 2, 2013 (UTC) ::@Wythagoras: \(\Sigma\) being admissible just means it is not a "round" ordinal. For example, if \(\alpha\) is admissible then \(\alpha + n\) is not admissible for finite \(n\). So no, it doesn't have to be larger than \(\omega_1^{\text{DEF}}\). ::@Ikosarakt1: The fact that \(\lambda\) is recursively inaccessible means it is greater than \(\omega_1^{\text{CK}}\), \(\omega_{\omega_1^{\text{CK}}}^{\text{CK}}\), Goucher's ordinal, and any recursive extension of that. Since \(\Sigma > \lambda\), it is greater than the same ordinals. Deedlit11 (talk) 22:30, October 2, 2013 (UTC) ::Is \(\lambda\) the smallest ordinal which is greater than any recursive extension of \(\alpha \mapsto \omega_\alpha^\text{CK}\)? In that case, lambda is equivalent to \(\omega_{1,2}^\text{CK}\) in my special notation for non-recursive ordinals. Ikosarakt1 (talk ^ ) 23:13, October 2, 2013 (UTC) ::It is very possible that you're right. Such ordinal is called recursively inaccessible, by analogy to inaccessible cardinals. LittlePeng9 (talk) 05:32, October 3, 2013 (UTC) :::It seems that \(\lambda\) is bigger than \(\omega_{1,2}^\text{CK}\). Quoting from Hamkins' and Lewis' paper on Infinite Time Turing Machines, :::Indescribability Theorem 8.3 The supremum λ of the writable ordinals is recursively inaccessible. Indeed, it is the λth recursively inaccessible ordinal, and the λth such fixed point, and so on. This is because λ is indescribable by Π-1-1 properties. Indeed, λ is indescribable by semi-decidable properties. :::The smallest recursively inaccessible ordinal is at least as big as \(\omega_{1,2}^\text{CK}\). (It might be bigger, I'm not sure.) Since λ is the λth recursively inaccessible ordinal, it must be bigger than \(\omega_{1,2}^\text{CK}\). :::The fact that λ is indescribable by decidable (even semi-decidable) properties, might mean it is forever beyond any extension of \(\omega_{1,2}^\text{CK}\) of the form Ikosarakt1 was contemplating. Deedlit11 (talk) 06:16, October 5, 2013 (UTC) Any way we can define fundamental sequences for lambda, zeta, and sigma? Do we observe all ITTMs up to a certain number of states? FB100Z • talk • 19:26, October 2, 2013 (UTC) :Yeah, it looks like setting \(\lambdan =\) the largest writable ordinal using an ITTM with at most \(n\) states is the way to go. (and similarly for \(\zeta\) and \(\Sigma\)). The only concern is whether you actually achieve the ordinal at some finite \(n\). I don't think this is a concern for \(\lambda\) or \(\zeta\) - we might be able to prove that the largest writable/eventually writable ordinal in n states gets larger as n increases - but I'm worried about \(\Sigma\). I think it may be possible that the supremum of accidentally writable ordinals is actually achieved for some ITTM. Deedlit11 (talk) 22:40, October 2, 2013 (UTC) How good are oracle ITTMs? FB100Z • talk • 05:36, October 3, 2013 (UTC) :Very strong. Again quoting from Hamkins' and Lewis' paper, :Jump Closure Theorem 5.4 Every infinite time degree is closed under the Turing jump operator. Indeed, for any real x and any writable ordinal α, the αth Turing jump of x is still infinite time equivalent to x. :So even a single infinite Turing jump will get you farther than any α regular Turing jumps, for any writable ordinal α. Note that there are two natural infinite Turing jumps: Given a real A, we can define :the "strong jump of A" = H^A = {(p,x) | φ^A_p (x) halts} :the "weak jump of A" = A ⊕ h^A = A ⊕ {p | φ^A_p (0) halts} :The strong jump should generate very fast-growing Busy Beaver functions! Deedlit11 (talk) 06:29, October 5, 2013 (UTC) Encoding ordinals as strings On the article I wrote that ordinals are expressible as strings, and here I want to propose such encoding (to verification): Let string 10000... encode 0. Now, if string \(w\) encodes ordinal \(\alpha\), then \(0w\) encodes it's successor (e.g. \(0^n1000...\) encodes finite ordinal n). For limit ordinals, let us have sequence of strings \(w_1,w_2,w_3,...\) encoding fundamental sequence for our ordinal. We use ruler sequence 1213121412131215... to code these strings as a single string: where there are 1's we put string \(w_1\), where there are 2's we put \(w_2\) etc. Now we put a single 1 on the beginning of string, so we won't mess up this with succesor ordinals. I think that using this encoding we can recover original ordinal from any proper encoding. LittlePeng9 (talk) 05:41, October 3, 2013 (UTC) :Interestingly, in the talk of article on \(\omega_1\), Deedlit proved that it is impossible to map all countable ordinals to irrationals in the way preserving order. So, can we disprove it? Ikosarakt1 (talk ^ ) 18:56, October 5, 2013 (UTC) ::Deedlit's proof is valid, as long as by real number ordering we take standard ordering induced by 0<1, a a+c We can create real number ordering such that my ordering, when interpreted as encoding after binary comma, is order preserving mapping f:w_1->(0,1). LittlePeng9 (talk) 20:04, October 5, 2013 (UTC) How large is \(\lambda\)? If the first recursively inaccessible is \(\omega^{CK}_{1,2}\), is the second then \(\omega^{CK}_{1,1,2}\), the third \(\omega^{CK}_{1,1,1,2}\) and the \(\omega\)th \(\omega^{CK}_{122}\)? If it is, \(\lambda\) seems to be equal to any extension using BAN or another array notation of \(\omega^{CK}_{122}\). Wythagoras (talk) 19:31, November 21, 2013 (UTC) If I had to guess, \(\lambda\) is well above that. LittlePeng9 (talk) 19:40, November 21, 2013 (UTC) :Formally, the second recursively inaccessible ordinal by \omega_\alpha^\text{CK} is \omega^{CK}_{1,2}+1 , third is \omega^{CK}_{1,2}+2 and \omega -th is \omega^{CK}_{1,2}+\omega . So we come to the conclusion: it isn't good to express ordinals as words. If we call something first # ordinal, it is unclear what we mean by the second # ordinal, third # ordinal, \omega -th # ordinal, 2-# ordinal (usually we differ that from second # ordinal which is yet more confusing), \omega -# ordinal, #-# ordinal, #-#-# ordinal, hyper-# ordinal, etc. (replace # by recursively inaccessible, inaccessible, admissible, uncountable, etc.) Ikosarakt1 (talk ^ ) 10:32, June 4, 2014 (UTC) ::Iko, you misunderstand concept of recursively inaccessible ordinals. First of all, such ordinal has to be limit ordinal, so \(\omega^\text{CK}_{1,2}+1\) clearly cannot be recursively inaccessible. Secondly, it must be limit of admissible ordinals, so it is at least as large, as \(\omega^\text{CK}_{\omega^\text{CK}_{1,2}+\omega}\). Thirdly, it must itself be admissible, which makes it really, really large. ::A correct way of thinking about recursively inaccessibles is as ordinals which cannot be reached from below, not from zero. This distinction is very important, because \(\omega^\text{CK}_{1,2}+1\) is easily accessible from below, namely from \(\omega^\text{CK}_{1,2}\). It isn't, however, accessible from zero, as if it was, so would be \(\omega^\text{CK}_{1,2}\). LittlePeng9 (talk) 13:59, June 4, 2014 (UTC) ::In that case, \beta -th recursively inaccessible ordinal must be \omega_{\beta,2}^\text{CK} in my notation. Ikosarakt1 (talk ^ ) 14:20, June 4, 2014 (UTC) It seems that \(\lambda\) well exceeds anything based on the function \(\alpha \mapsto \omega_\alpha^\text{CK}\). FB100Z • talk • 20:26, November 21, 2013 (UTC) :Yes, I see. It seems that \(\omega^{CK}_{1\text 3}\)\ as the \(\omega^{CK}_12\)th recursively inaccessible, and \\(\omega^{CK}_{1\text{|}_22}\)\ is the \(\omega^{CK}_2\)th recursively inaccessible. Wythagoras (talk) 08:18, November 24, 2013 (UTC) (kind of late reply) One of results of Hamkins and Lewis is that \(\lambda\) is not describable by \(\Pi^1_1\) (or even infinite time semidecidable) properties. I'm not 100% sure if that "transadmissible" hierarchy is definable in \(\Pi^1_1\), but it seems quite probable to me. And if that's true - let's say that \(\lambda\) is quite a big ordinal. LittlePeng9 (talk) 15:45, March 5, 2014 (UTC) ITTMs vs Rayo's function How does for example \(\Sigma1000\) compare to the ordinal that describes Rayo's function? Also, can someone find the first ordinal values of the function \(\Sigman\)? Wythagoras (talk) 07:37, February 16, 2014 (UTC) :From what I know, universe of accidentaly writable ordinals is quite uncharged territory, but for me it looks like ITTM's are strong enough to decide FOST formulas. If that's true, I guess Rayo's ordinal would be a writable ordinal. \(\Sigma1000\) looks like a huge ordinal, possibly outgrowing all writable ordinals. I wouldn't go va banque with that, but I say that Rayo's ordinal is small compared to \(\Sigma1000\). LittlePeng9 (talk) 22:19, February 16, 2014 (UTC) ::I would be very surprised if that was true. It seems reasonable that the ITTM ordinals are expressible in first-order set theory... FB100Z • talk • 05:35, February 17, 2014 (UTC) ::LittlePeng9: What if I say \(\lambda1000\)? Do you still think the same? And how about comparing second-order set theory or even type theory to \(\Sigma1000\)? ::FB100Z: What if I say oracle ITTMs? ::Here are my thoughts: ::Let \(\alpha\) be Rayo's ordinal. ::Let \(\beta\) be Fish number 7's ordinal. ::Let \(\gamma\) be the second-order set theory ordinal. ::Let \(\delta\) be the type theory ordinal. ::I would say: \(\lambda1000<\zeta1000<\alpha<\beta<\Sigma1000<\gamma<\delta\) ::I would place oracle ITTMs between \(\gamma\) and \(\delta\). ::Wythagoras (talk) 19:01, February 17, 2014 (UTC) (several months later) I just wanted to share my recent thoughts with you. Namely I came to the conclusion that ITTMs are indeed FOST-definable, and indeed so are oracle ITTMs for quite strong oracles. So, in my opinion, following ordering is valid: \(\lambda1000<\lambda<\zeta1000<\zeta<\Sigma<\alpha\) (I skipped \(\Sigma1000\) because there is no known fundamental sequence for it). LittlePeng9 (talk) 13:57, June 4, 2014 (UTC) Spot the difference Let \(N(x) = \alpha\) mean "\(x\) is a notation for \(\alpha\)." Consider the three following systems of ordinal notation: * N(an ITTM) = the ordinal written by that ITTM, given blank input (creating a notation up to \(\lambda\)) * N(an ITTM) = the ordinal clocked by that ITTM, given blank input (creating a notation up to \(\gamma\)) * N(an ITTM) = the ordinal eventually written by that ITTM, given blank input (creating a notation up to \(\zeta\)) Unfortunately accidental writing does not produce a unique ordinal. How can we create a notation up to \(\Sigma\)? FB100Z • talk • 05:20, March 6, 2014 (UTC) I'm afraid there is no really satisfying answer. One might consider N(an ITTM) to be the least upper bound of all ordinals accidentally written by that ITTM, but this is a bit meaningless, because then some machines would be a notations for \(\Sigma\), which we probably don't want. There is also a question if every acc. writable ordinal has a notation (it would not be the case if to write some ordinal \(\alpha\) we always had to use an ordinal \(\beta>\alpha\) and then "cut" the notation to leave only some initial fragment), which I don't know answer to. I don't think there are any "obvious" notations for all accidentally writable ordinals. LittlePeng9 (talk) 14:10, March 6, 2014 (UTC) : Speaking of that, I realized that the definition of fundamental sequence for \(\Sigma\) is invalid, as there is a single machine (with, say, \(N\) states) which accidentally writes all accidentally writable ordinal, thus making \(\SigmaN=\Sigma\) using our definition, which isn't proper fundamental sequence. Here is such machine: imagine a machine which at once simulates all possible ITTMs (Welsh called it universal ''machine), step by step. After each step it reads what real is (accidentally) written on tape of the first machine and copies it to output tape. Then the same with tape of the second machine, and the third etc. and after this we simulate next step of each machine. It's quite obvious that such machine exists and indeed accidentally writes all possible reals. Thus I'm removing the definition of \(\Sigman\). LittlePeng9 (talk) 16:58, March 6, 2014 (UTC) ::Aw shiiiieeeeet. Can we patch this up by disallowing such universal ITTMs? FB100Z • talk • 07:30, March 7, 2014 (UTC) :it's fine if some notations result in \(\Sigma\). we just label them as undefined (as we would do e.g. for non-halting TMs in the \(\lambda\) system). but your system has a far larger problem: i'm pretty sure it's the same as the one for \(\zeta\) :what if we supply both an ITTM and a time \(\tau\)? we get the notated ordinal by simulating the ITTM and looking at the tape at step \(\tau\). however this probably can't completely notate everything up to \(\Sigma\) due to the circularity of notating \(\tau\) itself FB100Z • talk • 07:30, March 7, 2014 (UTC) ::I believe \(\zeta\) is safe - every machine defines at most one eventually writable ordinal. As there is only finitely many machines with given number of states \(n\), number \(\zetan\) is exactly the largest of them. Because eventually writable ordinals are bounded from above by \(\zeta\) we have \(\zetan<\zeta\). ::If we were to notate accidentally writable ordinals as you explained, we would indeed meet circularity problem. There are accidentally writable reals which are not written until \(\zeta\), so we would have to use accidentally writable ordinals to define at which step we want to see some other real. Because \(\Sigma\) turned out to not be admissible, it might be a case that no "nice" definition of \(\Sigman\) exists. LittlePeng9 (talk) 12:24, March 7, 2014 (UTC) Real numbers Odd little trivia sidenote: LittlePeng's ruler sequence encoding lends to the following extremely cryptic surjective mapping from \(1\) onto the countable ordinals. * \(N(1) = 0\) * If \(N(x) = \alpha\), then \(N(x / 2) = \alpha + 1\). * If \(N(x_i) = \alpha_i\) for \(i < \omega\), then let \(s_0(x) = (\lfloor 2x \rfloor + 2x) / 4\) and \(s(x) = \lim_{n \rightarrow \infty} s_0^n(x)\). Then \(N \left( 1/2 + \sum_i 2^{-2^i} s^{i + 1}(x_i) \right) = \sup\{\alpha_i\}\). FB100Z • talk • 21:53, March 19, 2014 (UTC) :I think you need to check the last line; the last formula doesn't depend on \(x_i\). Also, won't s(x) = 0 whenever x < 1? Deedlit11 (talk) 05:13, March 20, 2014 (UTC) ::Nuts. What about \(s_0(x) = \lfloor 2x \rfloor + 2x\) and \(s(x) = \lim_{n \rightarrow \infty} 2^{-2n} s_0^n(x)\)? ::The effect of \(s(x)\) is to insert zeroes between the bits of the binary expansion of \(x\). So 0.abcdef... becomes 0.a0b0c0d0e0f0... FB100Z • talk • 18:47, March 20, 2014 (UTC) :::That formula still gives 0 always. I think \(s(x) = \lfloor 2x \rfloor / 2 + s(2x - \lfloor 2x \rfloor) / 4 \) should give what you want. I'm curious how you plain to use s(x). Deedlit11 (talk) 04:01, March 21, 2014 (UTC) large number function can we extract a large number function from this without directly using FGH? you're.so. 22:56, May 23, 2014 (UTC) Possibly. LittlePeng9 (talk) 04:23, May 24, 2014 (UTC) :Of course, just use HH, SGH or any other hierarchy you want. I don't think there is a way for defining fast-growing function without hierarchies in one form or another. Ikosarakt1 (talk ^ ) 10:35, June 4, 2014 (UTC) :You seem to have not noticed the link in my message above. LittlePeng9 (talk) 13:47, June 4, 2014 (UTC) :I noticed. The matter is, as I understand, that we can construct a hierarchy of TM's and define fast-growing functions from this. Say, let F_0(n) is a regular \Sigma(n) , F_1(n) is \Sigma(n) for Oracle TM's, F_m(n) is \Sigma(n) for m-order Oracle TM's, and so on. Ikosarakt1 (talk ^ ) 14:30, June 4, 2014 (UTC) :We indeed can, but how does it relate to paper I linked? Note that this paper doesn't refer to hierarchies in any way. LittlePeng9 (talk) 14:40, June 4, 2014 (UTC) :If it doesn't mention hierarchies explicitly it doesn't mean that they haven't been used. TREE function, SCG function, array notations seem to be independent from ordinals and hierarchies but their structures are still isomorphic to it. Ikosarakt1 (talk ^ ) 14:46, June 4, 2014 (UTC) :If you want to analyse everything to greatest detail, then you can find ordinals I guess all of the mathematics, and thus you can relate it to hierarchies. LittlePeng9 (talk) 14:55, June 4, 2014 (UTC) recursive ordinal test is there an ITTM that can test whether an ordinal is recursive? you're.so. 13:27, May 28, 2014 (UTC) We are given ordinal \(\alpha\). Make a machine which first writes \(\omega^\text{CK}_1\) and then compares these two ordinals. \(\alpha\) is recursive iff \(\alpha<\omega^\text{CK}_1\). LittlePeng9 (talk) 13:35, May 28, 2014 (UTC) :How do we compare two ordinals? you're.so. 15:11, June 4, 2014 (UTC) ::Suppose we are given two reals which code ordinals. We first look for the least element in ordering defined by each and we remove it. Now we simply repeat. We then look at which ordinal first "runs out", i.e. for which one we will delete all of the elements sooner, and that one is smaller. You can consider verifying correctness of this algorithm as a simple challenge (clue: first check that it correctly decides when ordinals are equal. Then look what happens when either ordinal becomes larger). LittlePeng9 (talk) 15:38, June 4, 2014 (UTC) Large countable ordinals From cardinality we can build some ordinals such as weakly inaccessible cardinals and weakly Mahlo cardinals. What about building some countable ordinals from admissibility such as recursively inaccessible ordinals and recursively mahlo ordinals, and something like that? And where do λ, ζ and Σ land? hyp$hyp?cos&cos (talk) 10:10, August 21, 2014 (UTC) :\(\lambda\) is recursively inaccessible, recursively Mahlo, has strong reflecting properties etc. Same applies to \(\zeta\). \(\Sigma\), while larger, isn't even admissible. LittlePeng9 (talk) 10:26, August 21, 2014 (UTC) Encoding What if we use the sequence "0010110111011110111110111111..." instead of "0010120123012340123450123456..."? Ikosarakt1 (talk ^ ) 17:40, February 16, 2015 (UTC) :I think you are missing the point what the digits mean - in the encoding 0010120123... the points marked with, say, 2 are meant to store contents of second simulated tape, and digits marked with 8 contents of 8th tape. Using your proposed way of encoding doesn't give a way to simulate more than two tapes. LittlePeng9 (talk) 18:14, February 16, 2015 (UTC) ::A lot of people appear to be misunderstanding the "0010120123012340123450123456..." notation, which is a sign that we probably need a clearer explanation -- ve 21:41, February 16, 2015 (UTC) FS section removed I have removed the fundamental sequence section. It's original research. It also isn't very useful because no FS system is provided for smaller ordinals. -- ve 21:15, August 30, 2015 (UTC) Multicolor ITTMs On the article it is stated that "To our knowledge, tapes with more than two colors have not been explored." Can multicolor ITTMs be simulated with ordinary ITTMs? -- ve 19:49, February 15, 2016 (UTC) :Should be possible. You make a universal ITTM and represent a cell on a tape with ''n colors as n'' subcells, and the ''k-th subcell is flashed iff the cell has color k''. Upon reaching the limit stage, you have a profile of which subcells flashed infinitely often, which can be used to compute the limit superior of the simulated ''n-color cell. It's not a formal argument but it's convincing enough to me. -- ve 20:02, February 15, 2016 (UTC) :I'm not sure what definition of multicolor ITTM you are adapting, but a natural one would be the following (and I suppose you imagine something along these lines too): tape can hold natural numbers between 0 and n-1 (inclusive), and at limit stages we are taking standard limsup of values. We can simulate them on standard ITTM with only finite delay as follows: each cell of simulated machine will use n-1 cells of simulator, and cell state k will be coded as 11...100...0 with k 1's. The advantage of this coding is that limsups compute themselves - at a limit stage the simulated cell will show correctly coded limsup of values. To simulate successor steps we use methods from normal (finite) TMs. This isn't quite formal either, but I think it illustrates the point well enough, and with enough persistence one could make it rigourous. LittlePeng9 (talk) 20:23, February 15, 2016 (UTC) ::Something like that. So the verdict is that multicolor ITTM's are no stronger than two-color ones. (Unless the ITTMs have infinitely many colors, in which case their transition table is infinite and a lot of other weirdness happens) -- ve 22:32, February 15, 2016 (UTC) About eventually accidentally writable ordinals Is there such as this? Is there a supremum of them? If so, is it uncountable? If not, is it larger than \(\Sigma\)? 15:07, November 20, 2017 (UTC) :It's not clear to me how such a thing would even be defined. Accidentally writable reals are supposed to appear at some point of the computation, while eventually writable ones are supposed to appear from some point on unchanged... how would one mix those two notions? —Preceding unsigned comment added by LittlePeng9 (talk • ) 17:17, November 20, 2017 (UTC) ::Simple: Accidental output may or may not be changed, so if accidental output is unchanged, it's eventual, thus it's eventually accidentally written. 15:09, November 21, 2017 (UTC) :::If an accidentally written output is never changed in the future, it is eventually written. So the eventually accidentally writable ordinals are just the eventually writable ordinals, with supremum \(\zeta<\Sigma\). LittlePeng9 (talk) 15:31, November 21, 2017 (UTC) Infinite time universal Turing machines Are they possible by logic? If so, what are their ordinals? Are there oracles of the infinite time universal Turing machines? If so, what are their ordinals? Is an \(n\)OITUTM (\(n\)th Oracle Infinite Time Universal Turing Machine) logically possible for \(n>0\)? 11:54, December 5, 2017 (UTC)